package dynamicprogramming;

/**
 * 假设你站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度。请你编程求出从最高层移动到最底层的最短路径长度。
 */

public class ShortestPath {
    private int[][] nodes = new int[][]{{5}, {7, 8}, {2, 3, 4}, {4, 9, 6, 1}, {2, 7, 9, 4, 5}};
    int minV = Integer.MAX_VALUE;

    private void getMinPath() {
        int[][] state = nodes.clone();

        for (int i = 1; i < state.length; i++) {
            state[i][0] += state[i - 1][0]; //该行第一个节点
            for (int j = 1; j < state[i].length - 1; j++) {
                state[i][j] += Math.min(state[i - 1][j], state[i - 1][j - 1]); // 前一行中，二选一，选最小那个
            }
            state[i][state[i].length - 1] += state[i - 1][state[i].length - 2]; //该行最后一个节点
        }

        for (int i = 0; i < state[state.length - 1].length; i++) {
            if (minV > state[state.length - 1][i]) {
                minV = state[state.length - 1][i];
            }
        }
        System.out.println("min value: " + minV);
//        show(state);

    }

    public static void show(int[][] array) {
        for (int[] ints : array) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {
        ShortestPath shortestPath = new ShortestPath();
        shortestPath.getMinPath();
    }
}
